package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/15 13:58
 *
 和为s的连续正数序列

9
[[2,3,4],[4,5]]

1,2,3,4,5,6,7,8,9
滑动窗口：使用双指针维护左右边界
开始l，r都在一个位置，
如果当前区间和比sum小，那么区间向右扩张；如果大，那么久收缩左边界；
 */

import java.util.ArrayList;

public class Main27 {
    //滑动窗口：双指针
    public ArrayList<ArrayList<Integer> > FindContinuousSequence2(int sum) {
        ArrayList<ArrayList<Integer>>ans=new ArrayList<>();
        if(sum==0)return ans;
        int l=1,r=1;
        for(;r<sum&&l<=r;){
            int t=(1+r)*(r-l+1)/2;
            System.out.println(t);
            if(t==sum){
                ArrayList<Integer>seq=new ArrayList<>();
                for(int i=l;i<=r;++i){
                    seq.add(i);
                }
                ans.add(seq);
                //注意：要改变区间否则会出现死循环
                l++;
            }else if(t<sum){
                r++;
            }else{
                l++;
            }
        }
        return ans;
    }
    //暴力枚举
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>>ans=new ArrayList<>();
        if(sum==0)return ans;
        //优化一下，枚举到一半就行
        for(int i=1;i<=sum/2;++i){
            int tmp=0;
            ArrayList<Integer>seq=new ArrayList<>();
            for(int j=i;j<=sum;++j){
                if(tmp==sum){
                    ans.add(seq);
                    break;
                }else if(tmp>sum)break;
                else{
                    seq.add(j);
                    tmp+=j;
                }
            }
        }
        return ans;
    }
}
